principal dual algorithm
head-to-head problem
The objective function of the main dual problem is the difference between the objective functions of the main problem and the dual problem, which is zero in the optimal solution. Also, the constraint condition is the combined constraint condition of the main problem and the dual problem.
Primal-dual
http://www.cs.toronto.edu/~slwang/primal-dual.pdf
https://img.atcoder.jp/agc043/editorial.pdf
http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H22-slide-iwata.pdf
http://www.akita-pu.ac.jp/system/elect/ins/kusakari/japanese/teaching/InfoMath/2008/note/14.pdf
Minimal Cost Flow (Primal-Dual) | Luzhiled's memo
least-cost current
---
This page is auto-translated from /nishio/主双対アルゴリズム. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.